package q1235_jobScheduling;

import java.util.Arrays;
import java.util.Comparator;

public class Solution_3 {
    /*
    先将工作排序，这次我们按照结束时间从小到大排序，然后定义 dp[i]，表示前 i 份工作中，可以获得的最大报酬。
    对于第 i 份工作，我们可以选择做，也可以选择不做。
    如果不做，最大报酬就是 dp[i]；
    如果做，我们可以通过二分查找，找到在第 i 份工作开始时间之前结束的最后一份工作，记为 j，
    那么最大报酬就是 profit[i] + dp[j]。取两者的较大值即可。即：

     */
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        var n = startTime.length;
        var jobs = new int[n][];
        for (var i = 0; i < n; ++i)
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[1])); // 按照结束时间排序

        var f = new int[n + 1];
        for (var i = 0; i < n; ++i) {
            var j = search(jobs, i, jobs[i][0]);
            f[i + 1] = Math.max(f[i], f[j + 1] + jobs[i][2]);
        }
        return f[n];
    }

    // 返回 endTime <= upper 的最大下标
    private int search(int[][] jobs, int right, int upper) {
        var left = -1;
        while (left + 1 < right) {
            var mid = (left + right) / 2;
            if (jobs[mid][1] <= upper) left = mid;
            else right = mid;
        }
        return left;
    }
}
